|
In mathematics, Ingleton's inequality is an inequality that is satisfied by the rank function of any representable matroid. In this sense it is a necessary condition for representability of a matroid over a finite field. Let ''M'' be a matroid and let ''ρ'' be its rank function, Ingleton inequality states that for any subsets ''X''1, ''X''2, ''X''3 and ''X''4 in the support of ''M'', the inequality :''ρ''(''X''1)+''ρ''(''X''2)+''ρ''(''X''1∪''X''2∪''X''3)+''ρ''(''X''1∪''X''2∪''X''4)+''ρ''(''X''3∪''X''4) ≤ ''ρ''(''X''1∪''X''2)+''ρ''(''X''1∪''X''3)+''ρ''(''X''1∪''X''4)+''ρ''(''X''2∪''X''3)+''ρ''(''X''2∪''X''4)'' is satisfied. Aubrey William Ingleton, an English mathematician, wrote an important paper in 1969 in which he surveyed the representability problem in matroids. Although the article is mainly expository, in this paper Ingleton stated and proved Ingleton's inequality, which has found interesting applications in information theory, matroid theory, and network coding. == Importance of inequality == There are interesting connections between matroids, the entropy region and group theory. Some of those connections are revealed by Ingleton's Inequality. Perhaps, the more interesting application of Ingleton's Inequality concerns the computation of network coding capacities. Linear coding solutions are constrained by the inequality and it has an important consequence: :The region of achievable rates using linear network coding could be, in some cases, strictly smaller than the region of achievable rates using general network coding.〔S.-Y. R. Li, R. W. Yeung, and N. Cai, “Linear network coding,” IEEE Trans. Inf. Theory, vol. 49, no. 2, pp. 371–381, Feb. 2003〕 For definitions see, e.g.〔Bassoli, R.B.; Marques, H.M.; Rodriguez, J.; KS Shum; R. T. Tafazolli; "Network Coding Theory: A Survey", IEEE Communications Surveys and Tutorials, Vol. 99, No. 0, pp. 1–29, February, 2013〕 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Ingleton's inequality」の詳細全文を読む スポンサード リンク
|